class Dist {
  public:
    int index;  // 节点的索引值，仅Dijkstra用的到
    int length; // 当前最短路径长度
    int pre;    // 路径最后经过的节点
};
void Dijkstra(Graph &G, int s, Dist *&D) // s是源点
{
    D = new Dist[G.VerticesNum()];
    for (int i = 0; i < G.VerticesNum(); i++) {
        D[i].index = i;
        D[i].length = INFINITE;
        D[i].pre = s;
    }
    D[s].length = 0;                // 源点到自身的路径长度设置为0
    MiniHeap<Dist> H(G.EdgesNum()); // 最小堆用于找出最短路径
    H.Insert(D[s]);
}
for (i = 0; i < G.VerticesNum(); i++) {
    bool FOUND = false;
    Dist d;
    while (!H.isEmpty()) {
        d = H.RemoveMin();
        if (G.Mark[d.index])
            == UNIVISTED {
                FOUND = true;
                break;
            }
    }
    if (!FOUND)
        break // 若没有符合条件的最短路径则跳出本次循环
            int v = d.index;
    G.Mark[v] = VISITED; // 将标记为设置为VISiTED//将标记位设置为VISITED
    for (Edge e = G.FristEdge(y); G.IsEdge(e); e = G.NextEdge(e)) // 刷新最短路
        D[G.ToVertex(e)].length = (D[v].length + G.Weight(e));
    D[G.ToVertex(e)].pre = v;
    H.Insert(D[G.ToVertex(e)]);
}
